#include "quick_sort.h"

namespace algo
{

void quick_sort(vector<int> &vctNums)
{
   if (vctNums.size() <= 1)
       return ;

   quick_sort_c(vctNums, 0, vctNums.size()-1);

}

void quick_sort_c(vector<int> &vctNums, int p, int r)
{
    if (p >= r)
        return ;

    int q = partition(vctNums, p, r);

    quick_sort_c(vctNums, p, q-1);
    quick_sort_c(vctNums, q+1, r);

}

int partition(vector<int> &vctNums, 
              int p, int r)
{
    int pivot = vctNums[r];
    int i = p;
    for (int j = p; j < r; ++j)
    {
        if (vctNums[j] < pivot)
        {
            swap(vctNums[i], vctNums[j]);
            ++i;
        }
    }
    swap(vctNums[i], vctNums[r]);
    return i;
}

}
